COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00015 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a17.tex[154,phy] \today\hfill}

\bigskip
\noindent{\bf A Sufficiency of Fallacies.}

In past years, students have turned in numerous fallacious answers to
problems on formal languages. The ones below are problems from the
Hopcroft and Ullman book; H~\&~U are not to be blamed for the answers.
If you don't see the fallacies, you are probably ready to commit some
yourself. The answers have been edited in minor ways.

\smallskip
Which of the following languages are regular sets? Prove your answer.
$$\{\,0↑m1↑n0↑{m+n}\mid m≥1\hbox{ and }n≥1\,\}=L\leqno\hbox{\bf (3.1b)}$$

Let $z=\underbrace{00}↓u\,\underbrace{11}↓v\,\underbrace{0000}↓w$.
Assume $L$ is regular; split into $uvw$. Then
$\underbrace{00}↓u\,\underbrace{1111}↓{v↑2}\,\underbrace{0000}↓w$ should
be in~$L$, by the pumping lemma, but is not.

\smallskip
\disleft 35pt:{\bf 3.1(d)}:
The set of all strings that do not have three consecutive 0's.

Let $L↓1=\Sigma↑{\ast}-L↓2=(0+1)↑{\ast}-(0+1)↑{\ast}000(0+1)↑{\ast}$,
where $L↓2=(0+1)↑{\ast}000(0+1)↑{\ast}$, then
$z=\underbrace{1}↓u\,\underbrace{000}↓v\,\underbrace{11}↓w\in L↓2$,
so $z↓2=\underbrace{00}↓u\,\underbrace{0000}↓{v↑2}\,\underbrace{11}↓w\in L↓2$.
By the pumping lemma, $L↓2$~is regular, and by Theorem~3.2 the class of
regular sets is closed under complementation, so $L↓1$~is regular.

\smallskip
\disleft 35pt:{\bf 3.1(e)}:
The set of all strings with an equal number of 0's and 1's.

One subset of this language is $L=0↑i1↑i$. Assume $L$ regular. Then let
$z=\underbrace{0}↓u\,\underbrace{00}↓v\,\underbrace{111}↓w\in L$;
by the pumping lemma, $z'=\underbrace{0}↓u\,\underbrace{0000}↓{v↑2}\,
\underbrace{111}↓w$ should be in~$L$, but is not. $L$~is not regular.
Since $L$ is a subset of the original language and regularity is closed
under union, $\{L$~with other language, $\subset$~original
language$\}$.
Not a regular set. [Last two sentences verbatim.]

\smallskip
\disleft 35pt:{\bf 3.2}:
Prove that there exists a constant $n$ such that for each
$z↓1$, $z↓2$, $z↓3$ with $z↓1z↓2z↓3$ in $L$ and $|z↓2|=n$,
$z↓2$~can be written $z↓2=uvw$ such that $|v|≥1$ and for each
$i≥0$, $z↓1uv↑iwz↓3$ is in~$L$. $L$~is a regular set.

$$L=\{\,z↓1z↓2z↓3\mid z↓1\in L↓1; z↓2\in L↓2; z↓3\in L↓3\,\}$$
Since $L$ is a regular set, so are $L↓1$, $L↓2$, and $L↓3$ by closure
under concatenation. Theorem~3.1. 

By the pumping lemma on $L↓2$,
$$\eqalign{|z↓2|&≥n↓2\cr
z↓2&=uvw\cr
|uv|&≤n↓2\cr
|v|&≥1\cr}$$
for all $i≥0$, $uv↑iw$ is in $L↓2$.

Since $|z↓2|≥n↓2$ and $n↓2≤$ \#\ states in a machine accepting~$L↓1$,
$|z↓2|=n$. Since $L↓2$ is regular and $uv↑iw$ is in~$L↓2$ and $L$~is
the concatenation of $L↓1$, $L↓2$, and~$L↓3$ and the class of regular
sets is closed under concatenation, $L$~is a regular set.

\vfill\eject

%\smallskip
\disleft 35pt:{\bf 3.3}:
Prove that $\{\,0↑j1↑m2↑m\mid i≥1,m≥1\,\}$ is non-regular.

$$\vcenter{\halign{$\rt{#}\;$&$\lft{#}$\qquad&\lft{#}\cr
z&=\underbrace{00}↓{z↓1}\,\underbrace{111}↓{z↓2}\,\underbrace{222}↓{z↓3}
&Assume $L$ regular.\cr
\noalign{\medskip}
z↓2&=\underbrace{1}↓u\,\underbrace{1}↓v\,\underbrace{1}↓w&By exercise 3.2.\cr
\noalign{\medskip}
&=\underbrace{00}↓{z↓1}\,\underbrace{1}↓u\,\underbrace{11}↓{v↑2}
\underbrace{1}↓w\,\underbrace{222}↓{z↓3}&By exercise 3.2 this should be
accepted by $L$\cr
&&but it is not since it is $0↑21↑42↑3$, $m≠n$.\cr
\noalign{\medskip}
&&CONTRADICTION. NON REGULAR.\cr}}$$

\smallskip
\disleft 35pt:{\bf 3.9}:
Is the class of regular sets closed under infinite union?

Yes it is. The class of regular sets is closed under union and so,
$$\bigl(\bigl(\bigl(\bigl((L↓0\cup L↓1)\cup L↓2\bigr)\cup L↓3\bigr)\cup L↓4
\ldots\cup L↓∞\bigr)=\bigcup↓{i=0}↑∞L↓i\,.$$

Each successive union can be considered to be the union of just two regular
languages, and so by Theorem~3.1 infinite union is closed under union.

\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft July 20, 1984


\bye